0961. 在长度 2N 的数组中找出重复 N 次的元素【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 暴力解法

1. 📝 题目描述

• leetcode

给你一个整数数组 nums，该数组具有以下属性：

• nums.length == 2 * n.
• nums 包含 n + 1 个不同的元素
• nums 中恰有一个元素重复 n 次

找出并返回重复了 n 次的那个元素。

---

示例 1：

输入：nums = [1,2,3,3]
输出：3

---

示例 2：

输入：nums = [2,1,2,5,3,2]
输出：2

---

示例 3：

输入：nums = [5,1,5,2,5,3,5,4]
输出：5

---

提示：

• 2 <= n <= 5000
• nums.length == 2 * n
• 0 <= nums[i] <= 10^4
• nums 由 n + 1 个 不同的 元素组成，且其中一个元素恰好重复 n 次

2. 🎯 s.1 - 暴力解法

js

/**
 * @param {number[]} nums
 * @return {number}
 */
var repeatedNTimes = function (nums) {
  const seen = new Set()
  for (const x of nums) {
    if (seen.has(x)) return x
    seen.add(x)
  }
  return -1 // 按题意不会到这里
}

• 时间复杂度：$O(n)$，遍历一次数组
• 空间复杂度：$O(n)$，使用集合记录已出现的元素

算法思路：

• 用哈希集合 seen 记录已经出现的数字
• 遍历数组，遇到第二次出现的数字立即返回，该数字即为重复了 n 次的元素
• 根据题意保证存在且唯一，因此线性扫描即可找到答案